package leetcode;

import java.util.Random;

public class LC135Candy {

    public static int candy(int[] ratings) {
        int[] cnt = new int[ratings.length];
        cnt[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i-1]) cnt[i] = cnt[i-1] + 1;
            else if (ratings[i] == ratings[i-1]) cnt[i] = 1;
            else { // cnt[i-1] > cnt[i]
                cnt[i] = 1;
                if (cnt[i - 1] == 1) {
                    int pre = i - 1;
                    while (pre >= 0 && ratings[pre] > ratings[pre + 1] && cnt[pre] <= cnt[pre + 1]) {
                        cnt[pre] = cnt[pre + 1] + 1;
                        pre --;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < ratings.length; i++) {
            ans += cnt[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(candy(new int[]{0,1,2,3,2,1}));
    }
}
